package com.zlk.algorithm.dataStructure.graph.buildSmallTree;

import com.zlk.algorithm.dataStructure.graph.impl.Edge;
import com.zlk.algorithm.dataStructure.graph.impl.Graph;
import com.zlk.algorithm.dataStructure.graph.impl.Node;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 // Prim算法模版（洛谷）
 // 动态空间实现
 // 测试链接 : https://www.luogu.com.cn/problem/P3366
 // 请同学们务必参考如下代码中关于输入、输出的处理
 // 这是输入输出处理效率很高的写法
 // 提交以下所有代码，把主类名改成Main，可以直接通过

 Prim算法（不算常用）
 1 解锁的点的集合叫set（普通集合）、解锁的边的集合叫heap（小根堆）。set和heap都为空。
 2 可从任意点开始，开始点加入到set，开始点的所有边加入到heap
 3 从heap中弹出权值最小的边e，查看边e所去往的点x
 A. 如果x已经在set中，边e舍弃，重复步骤3
 B. 如果x不在set中，边e属于最小生成树，把x加入set，重复步骤3
 4 当heap为空，最小生成树的也就得到了

 证明略！

 时间复杂度O(n + m) + O(m * log m)

 //
 **/
public class Prim {


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(reader);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken()!=-1){
            int N = (int) in.nval;
            in.nextToken();
            int M = (int) in.nval;
            int[][] edges = new int[500001][3];
            // x：  y：    z： 长度
            //下标1开始
            ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
            for (int i = 0; i <=N; i++) {
                graph.add(new ArrayList<>());
            }
            for (int i = 0, x, y, z; i < M; i++) {
                in.nextToken();
                x = (int) in.nval;
                in.nextToken();
                y = (int) in.nval;
                in.nextToken();
                z = (int) in.nval;
                graph.get(x).add(new int[]{y,z});
                graph.get(y).add(new int[]{x,z});
            }
            HashSet<Integer> set = new HashSet<>();
            int edgeCnt = 0;
            int ans =0;
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            set.add(1);
            for (int[] ints : graph.get(1)) {
                priorityQueue.add(ints);
            }

            while (!priorityQueue.isEmpty()){
                int[] poll = priorityQueue.poll();
                int w = poll[1];
                int nextN = poll[0];
                if(!set.contains(nextN)){
                    set.add(nextN);
                    ans+=w;
                    edgeCnt++;
                    for (int[] ints : graph.get(nextN)) {
                        priorityQueue.add(ints);
                    }
                }
            }
            out.println(edgeCnt == N-1 ? ans : "orz");
        }
        out.flush();
        out.close();
        reader.close();
    }






    //遍历所有点判断是否已经加入集合中，集合不存在就当前点发散的边遍历边加入优先队列中去
    //    遍历优先队列，找到toNode 如果toNode不在set集合中就将当前边加入result中去，然后依次将toNode发散
    //


    public Set<Edge> primMST(Graph graph) {
        // 解锁的边进入小根堆
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>((a,b)->{
            return a.weight-b.weight;
        });

        // 依次挑选的的边在result里
        Set<Edge> result = new HashSet<>();

        // 哪些点被解锁出来了
        HashSet<Node> nodeSet = new HashSet<>();
        for (Node value : graph.nodes.values()) {
            if(!nodeSet.contains(value)){
                nodeSet.add(value);
                for (Edge edge : value.edges) {
                    priorityQueue.add(edge);
                }
                while (!priorityQueue.isEmpty()) {
                    // 弹出解锁的边中，最小的边
                    Edge edge = priorityQueue.poll();
                    // 可能的一个新的点
                    Node toNode = edge.to;
                    // 不含有的时候，就是新的点
                    if (!nodeSet.contains(toNode)) {
                        nodeSet.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges) {
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }
        return result;
    }


}
